package Sort.sort2020_2;

/**
 * 归并排序
 * 从小到大
 * @author: leiwenkang
 * @date: 2020/5/23
 * @time: 18:17
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] array = {3,8,4,6,7,2,5,9,1};
        sort(array);
        for (int i = 0; i < array.length; i++){
            System.out.print(array[i]);
            System.out.print(" ");
        }
    }

    public static void sort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        mergeSort(array, 0, array.length - 1);
    }

    private static void mergeSort(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }

        int mid = (low + high) >> 1;
        //左边数组排序
        mergeSort(array, low, mid);
        //右边数组排序
        mergeSort(array, mid + 1, high);
        //合并左右数组
        mergeSort(array, low, mid, high);
    }

    private static void mergeSort(int[] array, int low, int mid, int high) {
        int[] thirdArr = new int[high - low + 1];

        int first = low;
        int second = mid + 1;
        int third = 0;

        while (first <= mid && second <= high) {
            if (array[first] <= array[second]) {
                thirdArr[third++] = array[first];
                first++;
            } else {
                thirdArr[third++] = array[second];
                second++;
            }
        }

        while (first <= mid) {
            thirdArr[third++] = array[first++];
        }

        while (second <= high) {
            thirdArr[third++] = array[second++];
        }

        //新数组覆盖老数组
        int i = 0;
        while (low <= high) {
            array[low++] = thirdArr[i++];
        }  
    }
}
